package com.sjf.day02.sort;

import java.util.Arrays;

/**
 * 基数排序
 *  定义二维数组实现，以空间换时间实现排序
 *
 *
 * @author <huangtang>
 * @since 2021/12/29 13:27
 **/
public class RadixSort {
    public static void main(String[] args) {
        int[] arr={53,3,542,-7,748,14,-30,214};
        //int[] arr = new int[100000];
        //for (int i = 0; i < 100000; i++) {
        //    arr[i] = (int)(Math.random() * 1000000); //生产 0 - 100000的随机数
        //}
        //long t1 = System.currentTimeMillis();

        //找出负数最大的使每个数+这个数的绝对值
        int min = 0;
        for (int i = 0; i < arr.length; i++) {
            min = Math.min(min,arr[i]);
        }
        for (int i = 0; i < arr.length; i++) {
            arr[i] = arr[i] + Math.abs(min) + 1;
        }
        redix(arr);
        for (int i = 0; i < arr.length; i++) {
            arr[i] -= Math.abs(min) + 1;
        }
        System.out.println(Arrays.toString(arr));
        //System.out.println("基数排序用时："+(System.currentTimeMillis()-t1));  //53ms
    }

    /**
     * 基数排序方法
     * @param arr
     */
    public static void redix(int[] arr){
        //定义一个二维数组表示10个桶
        int[][] bucket = new int[10][arr.length]; //arr.length防止极端情况下的数据溢出

        //第一轮排序,取个位数字

        //为了记录每个桶中，实际存放了多少数据
        //定义一个一维数组，下标代表第几个桶，值为几个有效数据
        int[] bucketElementCounts = new int[10];

        //进行几轮操作，取决于最大数的位数，遍历数组得到最大的数
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max,arr[i]);
        }
        int maxLength = (max+"").length(); //得到最大数的位数

        //for循环操作
        for (int k = 0; k < maxLength; k++) {
            //进行maxLength轮操作
            for (int i = 0; i < arr.length; i++) {
                //取出每个元素的k位数(个，十，百)
                int digit = arr[i] /(int)(Math.pow(10,k)) % 10;
                //放入到对应的桶中
                //digit 代表个位数对应的第几个桶
                //bucketElementCounts[digit] 代表对应桶的数个数，放完后需要对个数+1
                bucket[digit][bucketElementCounts[digit]++] = arr[i];
            }

            //将bucket桶中的数放回原数组arr中
            int index = 0;
            for (int i = 0; i < bucket.length; i++) {
                //如果桶中有数据,才放入arr中
                if(bucketElementCounts[i]!=0){
                    //循环第i个桶,依次放入arr中
                    for (int j = 0; j < bucketElementCounts[i]; j++) {
                        arr[index++] = bucket[i][j];
                    }
                }
                //第一轮处理后，需要将每一个bucketElementCounts置0
                bucketElementCounts[i] = 0;
            }

            //System.out.printf("第%d轮对个位排序输出%s \n",k,Arrays.toString(arr));
        }


        /*
            以下为推导过程
         */





        //for (int i = 0; i < arr.length; i++) {
        //    //取出每个元素的个位数
        //    int digit = arr[i] % 10;
        //    //放入到对应的桶中
        //    //digit 代表个位数对应的第几个桶
        //    //bucketElementCounts[digit] 代表对应桶的数个数，放完后需要对个数+1
        //    bucket[digit][bucketElementCounts[digit]++] = arr[i];
        //}
        //
        ////将bucket桶中的数放回原数组arr中
        //int index = 0;
        //for (int i = 0; i < bucket.length; i++) {
        //    if(bucketElementCounts[i]!=0){
        //        //如果桶中有数据,才放入arr中
        //        //循环第i个桶,依次放入arr中
        //        for (int j = 0; j < bucketElementCounts[i]; j++) {
        //            arr[index++] = bucket[i][j];
        //        }
        //    }
        //    //第一轮处理后，需要将每一个bucketElementCounts置0
        //    bucketElementCounts[i] = 0;
        //}
        //
        //System.out.println("第一轮对个位排序输出"+ Arrays.toString(arr));
        //
        ////第二轮排序
        //
        ////为了记录每个桶中，实际存放了多少数据
        ////定义一个一维数组，下标代表第几个桶，值为几个有效数据
        //for (int i = 0; i < arr.length; i++) {
        //    //取出每个元素的个位数
        //    int digit = arr[i] /10 %10;
        //    //放入到对应的桶中
        //    //digit 代表个位数对应的第几个桶
        //    //bucketElementCounts[digit] 代表对应桶的数个数，放完后需要对个数+1
        //    bucket[digit][bucketElementCounts[digit]++] = arr[i];
        //}
        //
        ////将bucket桶中的数放回原数组arr中
        //index = 0;
        //for (int i = 0; i < bucket.length; i++) {
        //    if(bucketElementCounts[i]!=0){
        //        //如果桶中有数据,才放入arr中
        //        //循环第i个桶,依次放入arr中
        //        for (int j = 0; j < bucketElementCounts[i]; j++) {
        //            arr[index++] = bucket[i][j];
        //        }
        //    }
        //    bucketElementCounts[i] = 0;
        //}
        //
        //System.out.println("第二轮对十位排序输出"+ Arrays.toString(arr));
        //
        ////第三轮
        ////为了记录每个桶中，实际存放了多少数据
        ////定义一个一维数组，下标代表第几个桶，值为几个有效数据
        //for (int i = 0; i < arr.length; i++) {
        //    //取出每个元素的个位数
        //    int digit = arr[i] /100 %10;
        //    //放入到对应的桶中
        //    //digit 代表个位数对应的第几个桶
        //    //bucketElementCounts[digit] 代表对应桶的数个数，放完后需要对个数+1
        //    bucket[digit][bucketElementCounts[digit]++] = arr[i];
        //}
        //
        ////将bucket桶中的数放回原数组arr中
        //index = 0;
        //for (int i = 0; i < bucket.length; i++) {
        //    if(bucketElementCounts[i]!=0){
        //        //如果桶中有数据,才放入arr中
        //        //循环第i个桶,依次放入arr中
        //        for (int j = 0; j < bucketElementCounts[i]; j++) {
        //            arr[index++] = bucket[i][j];
        //        }
        //    }
        //}
        //
        //System.out.println("第三轮对百位排序输出"+ Arrays.toString(arr));
    }
}
